#include <bits/stdc++.h>

using namespace std;

// 用递归函数排序栈
// 栈只提供push、pop、isEmpty三个方法
// 请完成无序栈的排序，要求排完序之后，从栈顶到栈底从小到大
// 只能使用栈提供的push、pop、isEmpty三个方法、以及递归函数
// 除此之外不能使用任何的容器，数组也不行
// 就是排序过程中只能用：
// 1) 栈提供的push、pop、isEmpty三个方法
// 2) 递归函数，并且返回值最多为单个整数

// 返回栈的深度
// 不改变栈的数据状况
int deep(stack<int>& st)
{
    if(st.empty()) return 0;
    int num = st.top();
    st.pop();
    int depth = deep(st) + 1;
    st.push(num);
    return depth;
}

// 从栈当前的顶部开始，往下数depth层
// 返回这deep层里的最大值
int maxValue(stack<int>& st, int depth)
{
    if(depth == 0) return INT_MIN;

    int num = st.top();
    st.pop();
    int restMax = maxValue(st, depth - 1);
    int mx = max(num, restMax);
    st.push(num);
    return mx;
}

// 从栈当前的顶部开始，往下数depth层，已知最大值是max了
// 返回，max出现了几次，不改变栈的数据状况
int times(stack<int>& st, int depth, int max)
{
    if(depth == 0) return 0;

    int num = st.top();
    st.pop();
    int restTimes = times(st, depth - 1, max);
    int time = restTimes + (num == max ? 1 : 0);
    st.push(num);
    return time;
}

// 从栈当前的顶部开始，往下数depth层，已知最大值是max，出现了k次
// 请把这k个最大值沉底，剩下的数据状况不变
void down(stack<int>& st, int depth, int max, int k)
{
    if(depth == 0)
    {
        for(int i = 0; i < k; ++i)
        {
            st.push(max);
        }
        return;
    }
    int num = st.top();
    st.pop();
    down(st, depth - 1, max, k);
    if(num != max) st.push(num);
}

void sort(stack<int>& st)
{
    int depth = deep(st);
    while(depth > 0)
    {
        int mx = maxValue(st, depth);
        int k = times(st, depth, mx);
        down(st, depth, mx, k);
        depth -= k;
    }
}

// 为了测试
// 生成随机栈
stack<int> randomStack(int n, int v)
{
    stack<int> st;
    for(int i = 0; i < n; ++i)
    {
        st.push(rand() % v);
    }
    return st;
}

// 为了测试
// 检测栈是不是从顶到底依次有序
bool isSorted(stack<int>& st)
{
    int step = INT_MIN;
    while(!st.empty())
    {
        if(step > st.top())
        {
            return false;
        }
        step = st.top();
        st.pop();
    }
    return true;
}

int main()
{
    srand(time(nullptr));

    stack<int> test{{1, 5, 4, 5, 3, 2, 3, 1, 4, 2}};
    sort(test);
    while(!test.empty())
    {
        cout << test.top() << " ";
        test.pop();
    }
    cout << endl;

    // 随机测试
    int N = 20;
    int V = 20;
    int testTimes = 200000;
    cout << "测试开始" << endl;
    for(int i = 0; i < testTimes; ++i)
    {
        int n = rand() % N;
        stack<int> st = randomStack(n, V);
        sort(st);
        if(!isSorted(st))
        {
            cout << "出错了" << endl;
            break;
        }
    }
    cout << "测试结束" << endl;

    return 0;
}